package test;

import java.util.Arrays;

/**
 * @author Marioszk
 * 马戏团人塔
 */
public class PersonTower_马戏团人塔 {

    public static void main(String[] args) {
        int[] height = new int[]{1, 2, 2, 3, 4};
        int[] weight = new int[]{4, 1, 2, 5, 7};
        System.out.println(bestSeqAtIndex(height, weight));
    }

    public static int bestSeqAtIndex(int[] height, int[] weight) {
        height = Arrays.stream(height).sorted().toArray();
        weight = Arrays.stream(weight).sorted().toArray();
        int hCount = 1;
        int wCount = 1;
        int j = Math.min(1, height.length - 1);
        int comIndex = -1;
        for (int i = 0; i < height.length - 1 && j < height.length; i++) {
            if (i == j) {
                break;
            }
            if (height[i] == height[j]) {
                comIndex = j;
                break;
            }
            hCount++;
            j++;
        }

        int k = Math.min(1, weight.length - 1);
        for (int i = 0; i < weight.length - 1 && k < weight.length; i++) {
            if (i == j) {
                break;
            }
            if (weight[i] == weight[k]) {
                comIndex = Math.max(comIndex, k);
                break;
            }
            wCount++;
            k++;
        }
        if (comIndex == -1) {
            return Math.min(hCount, wCount);
        }
        return Math.max(Math.min(hCount, wCount), height.length - comIndex);
    }

    public static int bestSeqAtIndex2(int[] height, int[] weight) {
        int len = height.length;

        int[][] person = new int[len][2];

        for (int i = 0; i < len; ++i) {
            person[i] = new int[]{height[i], weight[i]};
        }
        Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

        int[] dp = new int[len];

        int res = 0;

        for (int[] pair : person) {

            int i = Arrays.binarySearch(dp, 0, res, pair[1]);

            if (i < 0) {
                i = -(i + 1);
            }

            dp[i] = pair[1];

            if (i == res) {
                ++res;
            }
        }
        return res;
    }
}
